// https://leetcode.cn/problems/construct-string-from-binary-tree/

// 算法思路总结：
// 1. 递归前序遍历二叉树构建字符串表示
// 2. 根节点值必须包含在结果中
// 3. 左子树为空但右子树非空时需要保留空括号
// 4. 右子树为空时可以省略括号表示
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include <queue>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(const vector<string>& nodes) 
{
    if (nodes.empty() || nodes[0] == "null") return nullptr;
    
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    
    while (!q.empty() && i < nodes.size()) 
    {
        TreeNode* current = q.front();
        q.pop();
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->left = new TreeNode(stoi(nodes[i]));
            q.push(current->left);
        }
        i++;
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->right = new TreeNode(stoi(nodes[i]));
            q.push(current->right);
        }
        i++;
    }
    
    return root;
}

void printResult(const vector<vector<int>>& result) 
{
    cout << "[";
    for (int i = 0; i < result.size(); ++i) 
    {
        cout << "[";
        for (int j = 0; j < result[i].size(); ++j) 
        {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

class Solution 
{
public:
    string tree2str(TreeNode* root) 
    {
        if (root == nullptr)
        {
            return "";
        }

        string res = to_string(root->val);

        if (root->left || root->right)
        {
            res += "(";
            res += tree2str(root->left);
            res += ")";
        }

        if (root->right)
        {
            res += "(";
            res += tree2str(root->right);
            res += ")";
        }

        return res;
    }
};

int main()
{
    vector<string> nodes1 = {"1","2","3","4"};
    vector<string> nodes2 = {"1","2","3","null","4"};

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    Solution sol;

    cout << sol.tree2str(root1) << endl;
    cout << sol.tree2str(root2) << endl;

    return 0;
}